//克鲁斯卡尔算法
//按权对边进行排序，按顺序从小到大将边加入，如果造成循环则不加入，反之加入
//这里的检查循环就可以使用并查集了，如果本来就是一个连通分量里的，那么再加边的话就必然有循环了
//使用最小优先级队列一个个地插入边
//同时创建并查集对象
//在下面使用前面两者检查并插入mst最终需要返回的队列中
//这个算法的时间与eloge成正比
//普里姆算法
//从顶点零(或者某一个点)开始，一个个地找边
//这里一个个找边，找的是连接着树中所有点的边中的最小边
//加入一个点，加入这个点指向的所有边（除了连接到已经在树内的顶点的边）
//同时，加入一个点之后优先队列中指向这个点的边留下，但是之后，如果用到了这种边，要知道这个边其实是不可用的，不用并把他去掉，然后下一步重复
//代码就是，需要一个数组标记哪些点已经在树内了，需要一个优先队列返回权值最小的边，需要一个队列返回边
//然后有一个visit
//然后就是循环
//得到权值最小边
//如果两个点都被访问过了，那么continue，反之则加入这条边到队列，并且哪个点没被访问visit哪个点
//visit就是将点加入树内，同时将连接点的所有边（除了连接到已经在树内的顶点的边）加入优先队列
//时间复杂度和上面相同
//上面是lazy版本，实现效率更高，下面是eager版本，效率也很高，但是空间更小
//不同就是，对于每一个点，我们只维护最小的那条边，也就是说，如果后面再加入和这个点相关的边，如果后面加入的边更大，那么不加他，反之则替代原来的边
//具体操作后面再查吧
//这里还涉及到一个index priority queue
import java.util.Queue;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.UF;

public class MST {
    private Queue<Edge> mst;
    private double weight;

    public MST(EdgeWeightedGraph G)
    {
        MinPQ<Edge> pq=new MinPQ<Edge>();
        for(Edge edge:G.edges())
        {
            pq.insert(edge);
        }

        UF uf=new UF(G.V());
       
        while (!pq.isEmpty()&&mst.size()<G.V()-1) {
            Edge g=pq.delMin();
            int v=g.either();int w=g.other(v);

            if(!uf.connected(v, w))
            {
              mst.add(g);
              uf.union(v, w);
            }
            
        }
    }

    public Iterable<Edge> edges()
    {
      return mst;
    }

    // public double weight()
    // {

    // }
    
    public static void main(String[] args) {
        In in=new In();
        EdgeWeightedGraph g=new EdgeWeightedGraph(in);
        MST mst=new MST(g);
        for(Edge edge:mst.edges())
        {
            System.out.println(edge);
        }
        // System.out.println(mst.weight());
    }

}
